package com.learn.algorithm.divide_and_conquer;

/**
 * 归并分治的一般思路
 * <p>
 * 原理:
 * 1. 思考一个问题在大范围上的答案，是否等于左部分答案 + 右部分答案 + 跨越左右产生的答案
 * 2. 计算 '跨越左右产生的答案' 时，如果加上左右各自有序的设定，会不会获得计算的便利性
 * 3. 如果满足以上两点，那么一般情况下该问题可能被归并分治解决
 * 4. 求解答案的过程中只需要加入归并排序的过程即可，因为要让左右各自有序，来获得计算的便利性
 */
public class MergeDivideAndConquer {

    private static final int MAX = 50001;

    // 归并分治-小和问题 https://www.nowcoder.com/practice/edfe05a1d45c4ea89101d936cac32469
    // 数组i位置的小和: data[i]左侧的, 小于等于data[i]的所有数的和
    // 数组小和: 所有位置的小和的和
    private static final int[] help = new int[MAX];

    public static long minSum(int[] data) {
        return minSum(data, 0, data.length - 1);
    }

    public static long minSum(int[] data, int low, int high) {
        if (low == high) {
            return 0;
        }
        int mid = low + (high - low) / 2;
        return minSum(data, low, mid) + minSum(data, mid + 1, high) + merge(data, low, mid, high);
    }

    private static long merge(int[] data, int low, int mid, int high) {

        long ans = 0;
        for (int j = mid + 1, i = low, sum = 0; j <= high; j++) {
            while (i <= mid && data[i] <= data[j]) {
                sum += data[i++];
            }
            ans += sum;
        }

        int i = low;
        int k = low;
        int j = mid + 1;
        while (i <= mid && j <= high) {
            help[k++] = data[i] <= data[j] ? data[i++] : data[j++];
        }
        while (i <= mid) {
            help[k++] = data[i++];
        }
        while (j <= high) {
            help[k++] = data[j++];
        }

        for (k = low; k <= high; k++) {
            data[k] = help[k];
        }

        return ans;
    }

    // 归并分治-翻转对数量 https://leetcode.cn/problems/reverse-pairs
    // 对于给定数组nums 如果 i < j 且 nums[i] > 2 * nums[j]，则(i, j) 称作一个翻转对

    private static int count(int[] data) {
        return count(data, 0, data.length - 1);
    }

    private static int count(int[] data, int low, int high) {
        if (low == high) {
            return 0;
        }
        int mid = low + (high - low) / 2;
        return count(data, low, mid) + count(data, mid + 1, high) + merge2(data, low, mid, high);
    }

    private static int merge2(int[] data, int low, int mid, int high) {
        int ans = 0;
        for (int i = low, j = mid + 1; i <= mid; i++) {
            while (j <= high && (long) data[i] > (long) data[j] * 2) {
                j++;
            }
            ans += j - mid - 1;
        }

        int i = low;
        int k = low;
        int j = mid + 1;
        while (i <= mid && j <= high) {
            help[k++] = data[i] <= data[j] ? data[i++] : data[j++];
        }
        while (i <= mid) {
            help[k++] = data[i++];
        }
        while (j <= high) {
            help[k++] = data[j++];
        }

        for (k = low; k <= high; k++) {
            data[k] = help[k];
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(minSum(new int[]{1, 3, 5, 2, 4, 6}));
        System.out.println(count(new int[]{1, 3, 5, 2, 4, 6}));
    }
}
